{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #逆波兰表达式求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evalRPN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逆波兰表达式求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>根据<a href=\"https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437\" target=\"_blank\"> 逆波兰表示法</a>，求该后缀表达式的计算结果。</p>\n",
    "\n",
    "<p>有效的算符包括&nbsp;<code>+</code>、<code>-</code>、<code>*</code>、<code>/</code>&nbsp;。每个运算对象可以是整数，也可以是另一个逆波兰表达式。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>整数除法只保留整数部分。</li>\n",
    "\t<li>给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [&quot;2&quot;,&quot;1&quot;,&quot;+&quot;,&quot;3&quot;,&quot;*&quot;]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [&quot;4&quot;,&quot;13&quot;,&quot;5&quot;,&quot;/&quot;,&quot;+&quot;]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [&quot;10&quot;,&quot;6&quot;,&quot;9&quot;,&quot;3&quot;,&quot;+&quot;,&quot;-11&quot;,&quot;*&quot;,&quot;/&quot;,&quot;*&quot;,&quot;17&quot;,&quot;+&quot;,&quot;5&quot;,&quot;+&quot;]\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>\n",
    "该算式转化为常见的中缀算术表达式为：\n",
    "  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5\n",
    "= ((10 * (6 / (12 * -11))) + 17) + 5\n",
    "= ((10 * (6 / -132)) + 17) + 5\n",
    "= ((10 * 0) + 17) + 5\n",
    "= (0 + 17) + 5\n",
    "= 17 + 5\n",
    "= 22</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tokens.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>tokens[i]</code> 要么是一个算符（<code>&quot;+&quot;</code>、<code>&quot;-&quot;</code>、<code>&quot;*&quot;</code> 或 <code>&quot;/&quot;</code>），要么是一个在范围 <code>[-200, 200]</code> 内的整数</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>逆波兰表达式：</strong></p>\n",
    "\n",
    "<p>逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>平常使用的算式则是一种中缀表达式，如 <code>( 1 + 2 ) * ( 3 + 4 )</code> 。</li>\n",
    "\t<li>该算式的逆波兰表达式写法为 <code>( ( 1 2 + ) ( 3 4 + ) * )</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>逆波兰表达式主要有以下两个优点：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>去掉括号后表达式无歧义，上式即便写成 <code>1 2 + 3 4 + * </code>也可以依据次序计算出正确结果。</li>\n",
    "\t<li>适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 150&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/\">https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [8Zf90G](https://leetcode.cn/problems/8Zf90G/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [8Zf90G](https://leetcode.cn/problems/8Zf90G/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        notes, stack = '+-*/', []\n",
    "        tokens.reverse()\n",
    "        while tokens:\n",
    "            a = tokens.pop()\n",
    "            if a in notes:\n",
    "                p_1, p_2 = int(stack[-2]), int(stack[-1])\n",
    "                stack = stack[:-2]\n",
    "                if a == '+':\n",
    "                    stack.append(p_1+p_2)\n",
    "                elif a == '-':\n",
    "                    stack.append(p_1-p_2)\n",
    "                elif a == '*':\n",
    "                    stack.append(p_1*p_2)\n",
    "                elif a == '/':\n",
    "                    stack.append(int(p_1/p_2))\n",
    "            else:\n",
    "                stack.append(a)\n",
    "        return int(stack[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        notes, stack = '+-*/', []\n",
    "        tokens.reverse()\n",
    "        while tokens:\n",
    "            a = tokens.pop()\n",
    "            if a in notes:\n",
    "                p_1, p_2 = int(stack[-2]), int(stack[-1])\n",
    "                stack = stack[:-2]\n",
    "                if a == '+':\n",
    "                    stack.append(p_1+p_2)\n",
    "                elif a == '-':\n",
    "                    stack.append(p_1-p_2)\n",
    "                elif a == '*':\n",
    "                    stack.append(p_1*p_2)\n",
    "                elif a == '/':\n",
    "                    stack.append(int(p_1/p_2))\n",
    "            else:\n",
    "                stack.append(a)\n",
    "        return int(stack[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = ['']*len(tokens)\n",
    "        top = -1\n",
    "\n",
    "        for i in tokens:\n",
    "            if i in '+-*/':\n",
    "                b = stack[top]\n",
    "                top -= 1\n",
    "                a = stack[top]\n",
    "                top -= 1\n",
    "                if i=='+':\n",
    "                    c = a+b\n",
    "                if i=='-':\n",
    "                    c = a-b\n",
    "                if i=='*':\n",
    "                    c = a*b\n",
    "                if i=='/':\n",
    "                    c = int(a/b)\n",
    "                top += 1\n",
    "                stack[top] = c \n",
    "            else:\n",
    "                top += 1\n",
    "                stack[top] = int(i)\n",
    "        return stack[top]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        tmp = []\n",
    "        for v in tokens:\n",
    "            if v in ['+', '-', '*', '/']:\n",
    "                a, b = tmp[-2], tmp[-1]\n",
    "                tmp = tmp[:-2]\n",
    "                c = a + b\n",
    "                if v == '-':\n",
    "                    c = a - b\n",
    "                if v == '*':\n",
    "                    c = a * b\n",
    "                if v == '/':\n",
    "                    c = int(a / b)\n",
    "                tmp.append(c)\n",
    "            else:\n",
    "                tmp.append(int(v))\n",
    "        return tmp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        s = ['+', '-', '*', '/']\n",
    "        for item in tokens:\n",
    "            if item in s:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if item == '+':\n",
    "                    stack.append(b+a)\n",
    "                elif item == '-':\n",
    "                    stack.append(b-a)\n",
    "                elif item == '/':\n",
    "                    stack.append(int(b/a))\n",
    "                elif item == '*':\n",
    "                    stack.append(b*a)\n",
    "            else:\n",
    "                stack.append(int(item))\n",
    "        return stack[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack, sign = [], '+-*/'\n",
    "        for i in tokens:\n",
    "            if i not in sign:stack.append(i)\n",
    "            else:\n",
    "                num1, num2 = stack.pop(), stack.pop()\n",
    "                stack.append(str(int(eval(num2 + i + num1))))\n",
    "        return int(stack.pop())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            if i in '+-*/':\n",
    "                op2 = int(stack.pop())\n",
    "                op1 = int(stack.pop())\n",
    "                if i == '+':\n",
    "                    stack.append(op1 + op2)\n",
    "                elif i == '-':\n",
    "                    stack.append(op1 - op2)\n",
    "                elif i == '*':\n",
    "                    stack.append(op1 * op2)\n",
    "                elif i == '/':\n",
    "                    stack.append(int(op1 / op2))\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return int(stack[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        op_to_binary_fn = {\n",
    "            \"+\": add,\n",
    "            \"-\": sub,\n",
    "            \"*\": mul,\n",
    "            \"/\": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致\n",
    "        }\n",
    "\n",
    "        stack = list()\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)\n",
    "            except ValueError:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                num = op_to_binary_fn[token](num1, num2)\n",
    "            finally:\n",
    "                stack.append(num)\n",
    "            \n",
    "        return stack[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # '/': lambda x, y: int(x / y)\n",
    "    op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)}\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token not in ['+',\"-\",\"*\",\"/\"]:\n",
    "                stack.append(int(token))\n",
    "            else:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append(self.op_map[token](num1, num2))\n",
    "        return stack.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        arr=[]\n",
    "        for i in tokens:\n",
    "            if i!='+' and i!='-' and i!='*' and i!='/':\n",
    "                 arr.append(int(i))\n",
    "            else:\n",
    "                a=arr.pop()\n",
    "                b=arr.pop()\n",
    "                if i=='+':\n",
    "                    c=a+b\n",
    "                elif i=='-':\n",
    "                    c=b-a\n",
    "                elif i=='*':\n",
    "                    c=a*b\n",
    "                elif i=='/':\n",
    "                    c=int(b/a)\n",
    "                arr.append(c)\n",
    "            #print(arr)\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack1=[]\n",
    "        for i in tokens:\n",
    "            if i not in [\"+\",\"-\",\"*\",\"/\"]:\n",
    "                stack1.append(int(i))\n",
    "            else:\n",
    "                a=stack1.pop()\n",
    "                b=stack1.pop()\n",
    "                if i ==\"+\":\n",
    "                    tmp=a+b\n",
    "                elif i==\"-\":\n",
    "                    tmp=b-a\n",
    "                elif i==\"*\":\n",
    "                    tmp=a*b\n",
    "                else:\n",
    "                    tmp=int(b/a)\n",
    "                stack1.append(tmp)\n",
    "        return stack1[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        stk = []\n",
    "\n",
    "        sig = ['+', '-', '*', '/']\n",
    "\n",
    "        for a in tokens:\n",
    "            if a in sig:\n",
    "                x,y = stk[-2], stk[-1]\n",
    "                stk = stk[:-2]\n",
    "                if a == '+':\n",
    "                    stk.append(x+y)\n",
    "                elif a == '-':\n",
    "                    stk.append(x-y)\n",
    "                elif a == '*':\n",
    "                    stk.append(x*y)\n",
    "                elif a == '/':\n",
    "                    stk.append(int(x/y))\n",
    "            else:\n",
    "                stk.append(int(a))\n",
    "        return stk[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        # 如果是数字就入栈, 如果是运算符就取栈顶元素操作\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if token == \"+\":\n",
    "                    stack.append(int(a) + int(b))\n",
    "                if token == \"*\":\n",
    "                    stack.append(int(a) * int(b))\n",
    "                if token == \"-\":\n",
    "                        stack.append(int(b) - int(a))\n",
    "                if token == \"/\":\n",
    "                        stack.append(int(b) / int(a))\n",
    "            else:\n",
    "                    stack.append(token)\n",
    "        return int(stack[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "                # 在此添加你的代码\n",
    "        st = []\n",
    "        for c in tokens:\n",
    "            if c in ['+','-','*','/']:\n",
    "                right = int(st.pop())\n",
    "                left = int(st.pop())\n",
    "                if c == '+':\n",
    "                    st.append(left+right)\n",
    "                    continue\n",
    "                if c == '-':\n",
    "                    st.append(left-right)\n",
    "                    continue\n",
    "                if c == '*':\n",
    "                    st.append(left*right)\n",
    "                    continue\n",
    "                if c == '/':\n",
    "                    st.append(left/right)\n",
    "                    continue\n",
    "            st.append(int(c))\n",
    "        return int(st[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        res=0\n",
    "        l=len(tokens)\n",
    "        stack=[]\n",
    "        i=0\n",
    "        while i<l:\n",
    "            if tokens[i].isnumeric():\n",
    "                stack.append(int(tokens[i]))\n",
    "            elif tokens[i][0]=='-' and tokens[i][1:].isnumeric():\n",
    "                stack.append(-1*int(tokens[i][1:]))\n",
    "            else:\n",
    "                a2=stack.pop()\n",
    "                a1=stack.pop()\n",
    "                if tokens[i]=='+':\n",
    "                    stack.append(a1+a2)\n",
    "                elif tokens[i]=='-':\n",
    "                    stack.append(a1-a2)\n",
    "                elif tokens[i]=='*':\n",
    "                    stack.append(a1*a2)\n",
    "                else:\n",
    "                    if a1*a2>0:\n",
    "                        stack.append(a1//a2)\n",
    "                    else:\n",
    "                        stack.append(abs(a1)//abs(a2)*(-1))\n",
    "            i+=1\n",
    "        return stack[0]    \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens) -> int:\n",
    "        list=[]\n",
    "        for i in tokens:\n",
    "            if (i >='0' and i<='9') or len(i)>1:\n",
    "                list.append(int(i))\n",
    "            else:\n",
    "                b=list.pop()\n",
    "                a=list.pop()\n",
    "                if i=='-':\n",
    "                    list.append(a-b)\n",
    "                elif i=='+':\n",
    "                    list.append(a+b)\n",
    "                elif i=='*':\n",
    "                    list.append(a*b)\n",
    "                elif i=='/':\n",
    "                    list.append(math.trunc(a/b))\n",
    "        return list.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        opDict = {\"+\": lambda x,y: x + y, \"-\": lambda x,y: x - y, \"*\": lambda x,y: x * y, \"/\": lambda x,y: int(x / y)}\n",
    "        numStack = []\n",
    "        for token in tokens:\n",
    "            if token in opDict:\n",
    "                right = numStack.pop()\n",
    "                left = numStack.pop()\n",
    "                numStack.append(opDict[token](left, right))            \n",
    "            else:\n",
    "                numStack.append(int(token))\n",
    "        return numStack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        nums_input = []\n",
    "        pattern = \"-?[0-9]+\"\n",
    "        for t in tokens:\n",
    "            res = re.match(pattern, t)\n",
    "            if res:\n",
    "                nums_input.append(int(t))\n",
    "            else:\n",
    "                num1 =  nums_input.pop()\n",
    "                num2 =  nums_input.pop()\n",
    "                result = eval(str(num2) + t + str(num1))\n",
    "                nums_input.append(int(result))\n",
    "        return nums_input[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        calc = {\n",
    "            '+':lambda x,y : x+y,\n",
    "            '-':lambda x,y : x-y,\n",
    "            '*':lambda x,y : x*y,\n",
    "            '/':lambda x,y : int(x/y),\n",
    "        }\n",
    "        for token in tokens:\n",
    "            if token in calc:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append(calc[token](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in [\"+\",\"-\",\"*\",\"/\"]:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if token == \"+\":\n",
    "                    stack.append(int(a)+int(b))\n",
    "                if token == \"-\":\n",
    "                    stack.append(int(b)-int(a))\n",
    "                if token == \"*\":\n",
    "                    stack.append(int(a)*int(b))\n",
    "                if token == \"/\":\n",
    "                    stack.append(int(b)/int(a))\n",
    "            else:\n",
    "                stack.append(token)\n",
    "        return int(stack[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        ans = []\n",
    "        for num in tokens:\n",
    "            if num not in '+-*/':\n",
    "                ans.append(num)\n",
    "            else:\n",
    "                a = ans.pop()\n",
    "                b = ans.pop()\n",
    "                if num == '+': ans.append(int(a)+int(b))\n",
    "                elif num == '-': ans.append(int(b)-int(a))\n",
    "                elif num == '*': ans.append(int(b)*int(a))\n",
    "                else: ans.append(int(b)/int(a))\n",
    "        return int(ans[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evalRPN(self, tokens) -> int:\n",
    "        op_to_binary_fn = {\n",
    "            \"+\": lambda x, y: int(x + y),\n",
    "            \"-\": lambda x, y: int(x - y),\n",
    "            \"*\": lambda x, y: int(x * y),\n",
    "            \"/\": lambda x, y: int(x / y),  # 需要注意 python 中负数除法的表现与题目不一致\n",
    "        }\n",
    "\n",
    "        stack = list()\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)\n",
    "            except :\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                num = op_to_binary_fn[token](num1, num2)\n",
    "            finally:\n",
    "                stack.append(num)\n",
    "\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stacks = []\n",
    "        cals = {'+' : lambda x, y : x + y,\n",
    "                '-' : lambda x, y : x - y,\n",
    "                '*' : lambda x, y : x * y,\n",
    "                '/' : lambda x, y : int(x / y),\n",
    "                }\n",
    "        for i in tokens:\n",
    "            if i in cals:\n",
    "                num2, num1 = stacks.pop(), stacks.pop()\n",
    "                stacks.append(cals[i](num1, num2))\n",
    "            else:\n",
    "                stacks.append(int(i))\n",
    "        return stacks[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.stack=[]\n",
    "    def push(self,elem):\n",
    "        self.stack.append(elem)\n",
    "    def pop(self):\n",
    "        cur= self.stack[-1]\n",
    "        del self.stack[-1]\n",
    "        return cur\n",
    "    # def get_top(self):\n",
    "    #     if len(self.stack)>0:\n",
    "    #         return self.stack[-1]\n",
    "    #     else:\n",
    "    #         return None\n",
    "    def is_empty(self):\n",
    "        return len(self.stack)==0\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = Stack()\n",
    "        a = ['+','-','*','/']\n",
    "        for i in range(len(tokens)):\n",
    "            #if tokens[i]==\"+\"or\"-\"or\"*\"or\"/\":\n",
    "            if tokens[i] in a:\n",
    "                #num1 = stack.get_top()\n",
    "                num1 = stack.pop()\n",
    "                num2 = stack.pop()\n",
    "                if tokens[i]==\"+\":\n",
    "                    stack.push(num2+num1)\n",
    "                if tokens[i]==\"-\":\n",
    "                    stack.push(num2-num1)\n",
    "                if tokens[i]==\"*\":\n",
    "                    stack.push(num2*num1)\n",
    "                if tokens[i]==\"/\":\n",
    "                    stack.push(int(num2/num1))\n",
    "            else:\n",
    "                stack.push(int(tokens[i]))\n",
    "        result = stack.pop()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        s = []\n",
    "        res = 0 \n",
    "        for token in tokens:\n",
    "            if token[-1].isdigit():\n",
    "                s.append(int(token))\n",
    "            else:\n",
    "                a, b = s.pop(), s.pop()\n",
    "                if token == \"+\": s.append(a + b)\n",
    "                if token == \"-\": s.append(b - a)\n",
    "                if token == \"*\": s.append(a * b)\n",
    "                if token == \"/\": s.append(int(b / a))\n",
    "        return s[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        ops = {'+', '-', '*', '/'}\n",
    "        for s in tokens:\n",
    "            if s in ops:\n",
    "                op2 = stack.pop()\n",
    "                op1 = stack.pop()\n",
    "                if s == '+':\n",
    "                    res = op1 + op2\n",
    "                elif s == '-':\n",
    "                    res = op1 - op2\n",
    "                elif s == '*':\n",
    "                    res = op1 * op2\n",
    "                else:\n",
    "                    res = int(op1 / op2)\n",
    "                stack.append(res)\n",
    "            else:\n",
    "                stack.append(int(s))\n",
    "        return stack[-1]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        steak = []\n",
    "        l = len(tokens)\n",
    "        for i in range(l):\n",
    "            if tokens[i] == \"+\":\n",
    "                steak[-1] += steak[-2]\n",
    "                steak[-2] = steak[-1]\n",
    "                steak.pop(-1)\n",
    "            elif tokens[i] == '-':\n",
    "                steak[-1] = steak[-2] - steak[-1]\n",
    "                steak[-2] = steak[-1]\n",
    "                steak.pop(-1) \n",
    "            elif tokens[i] == '*':\n",
    "                steak[-1] *= steak[-2]\n",
    "                steak[-2] = steak[-1]\n",
    "                steak.pop(-1)\n",
    "            elif tokens[i] == '/':\n",
    "                steak[-1] = int(steak[-2]/steak[-1])\n",
    "                steak[-2] = steak[-1]\n",
    "                steak.pop(-1)\n",
    "            else:\n",
    "                steak.append(int(tokens[i]))\n",
    "        return steak[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        operator = (\"+\", \"-\", \"*\", \"/\")\n",
    "\n",
    "        for token in tokens:\n",
    "            if token not in operator:\n",
    "                stack.append(token)\n",
    "            else:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append( str( int(eval(num1+token+num2)) ) ) \n",
    "        return int(stack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        calc = {\n",
    "            '+': lambda x, y:x + y,\n",
    "            '-': lambda x, y:x - y,\n",
    "            '*': lambda x, y:x * y,\n",
    "            '/': lambda x, y: int(x / y),\n",
    "        }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(),stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evalRPN(self, tokens) -> int:\n",
    "        op_to_binary_fn = {\n",
    "            \"+\": lambda x, y: int(x + y),\n",
    "            \"-\": lambda x, y: int(x - y),\n",
    "            \"*\": lambda x, y: int(x * y),\n",
    "            \"/\": lambda x, y: int(x / y),  # 需要注意 python 中负数除法的表现与题目不一致\n",
    "        }\n",
    "\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)\n",
    "            except:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                num = op_to_binary_fn[token](num1, num2)\n",
    "            finally:\n",
    "                stack.append(num)\n",
    "\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        calc = {\n",
    "            '+': lambda y, x: x + y,\n",
    "            '-': lambda y, x: x - y,\n",
    "            '*': lambda y, x: x * y,\n",
    "            '/': lambda y, x: int(x / y)\n",
    "        }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                stack.append(calc[i](stack.pop(), stack.pop()))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        opDict = {\"+\": lambda x,y: x + y, \"-\": lambda x,y: x - y, \"*\": lambda x,y: x * y, \"/\": lambda x,y: int(x / y)}\n",
    "        numStack = []\n",
    "        for token in tokens:\n",
    "            if token in opDict:\n",
    "                right = numStack.pop()\n",
    "                left = numStack.pop()\n",
    "                numStack.append(opDict[token](left, right))            \n",
    "            else:\n",
    "                numStack.append(int(token))\n",
    "        return numStack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in ['+', '-', '*', '/']:\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                if token == '+':\n",
    "                    stack.append(a + b)\n",
    "                elif token == '-':\n",
    "                    stack.append(a - b)\n",
    "                elif token == '*':\n",
    "                    stack.append(a * b)\n",
    "                elif token == '/':\n",
    "                    stack.append(int(a / b))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for t in tokens:\n",
    "            if t == '+':\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                stack.append(a+b)\n",
    "            elif t == '-':\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                stack.append(a-b)\n",
    "            elif t == '*':\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                stack.append(a*b)\n",
    "            elif t == '/':\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                stack.append(int(a/b))\n",
    "            else:\n",
    "                stack.append(int(t))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        cup=[]\n",
    "        for i in tokens:\n",
    "            if i=='+':\n",
    "                a=cup.pop()+cup.pop()\n",
    "                cup.append(a)\n",
    "            elif i=='-':\n",
    "                a=cup.pop(-2)-cup.pop(-1)\n",
    "                cup.append(a)\n",
    "            elif i=='*':\n",
    "                a=cup.pop()*cup.pop()\n",
    "                cup.append(a)\n",
    "            elif i=='/':\n",
    "                a=int(cup.pop(-2)/cup.pop(-1))\n",
    "                cup.append(a)\n",
    "            else:\n",
    "                cup.append(int(i))\n",
    "        return int(cup[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        n = len(tokens)\n",
    "        st = []\n",
    "        for s in tokens:\n",
    "            if s not in ['/', '*', '+', '-']:\n",
    "                st.append(int(s))\n",
    "                continue\n",
    "            num1 = st.pop()\n",
    "            num2 = st.pop()\n",
    "            st.append(int(eval(f'{num2}{s}{num1}')))\n",
    "        return st.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        # 如果是数字就入栈, 如果是运算符就取栈顶元素操作\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if token == \"+\":\n",
    "                    stack.append(int(a) + int(b))\n",
    "                elif token == \"*\":\n",
    "                    stack.append(int(a) * int(b))\n",
    "                elif token == \"-\":\n",
    "                    stack.append(int(b) - int(a))\n",
    "                else:\n",
    "                    stack.append(int(b) / int(a))\n",
    "            else:\n",
    "                stack.append(token)\n",
    "        return int(stack[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        s = []\n",
    "        for t in tokens:\n",
    "            if t == '+':\n",
    "                a, b = s[-1], s[-2]\n",
    "                s.pop()\n",
    "                s.pop()\n",
    "                s.append(a + b)\n",
    "            elif t == '-':\n",
    "                a, b = s[-1], s[-2]\n",
    "                s.pop()\n",
    "                s.pop()\n",
    "                s.append(b - a)\n",
    "            elif t == '*':\n",
    "                a, b = s[-1], s[-2]\n",
    "                s.pop()\n",
    "                s.pop()\n",
    "                s.append(a * b)\n",
    "            elif t == '/':\n",
    "                a, b = s[-1], s[-2]\n",
    "                s.pop()\n",
    "                s.pop()\n",
    "                s.append(int(b / a))\n",
    "            else:\n",
    "                s.append(int(t))\n",
    "        return s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stk = []\n",
    "        for t in tokens:\n",
    "            if t in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                num1 = stk.pop()\n",
    "                num2 = stk.pop()\n",
    "                if t == \"+\":\n",
    "                    stk.append(num1 + num2)\n",
    "                elif t == \"-\":\n",
    "                    stk.append(num2 - num1)\n",
    "                elif t == \"*\":\n",
    "                    stk.append(num1 * num2)\n",
    "                elif t == \"/\":\n",
    "                    stk.append(int(num2 / num1))\n",
    "            else:\n",
    "                stk.append(int(t))\n",
    "        return stk[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        operator = {\n",
    "            \"+\": lambda x, y: x + y,\n",
    "            \"-\": lambda x, y: x - y,\n",
    "            \"*\": lambda x, y: x * y,\n",
    "            \"/\": lambda x, y: int(x / y)\n",
    "        }\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for token in tokens:   \n",
    "            if token in operator:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append(operator[token](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        \n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "\n",
    "        for token in tokens:\n",
    "            if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):\n",
    "                stack.append(int(token))\n",
    "            else:\n",
    "                operand2 = stack.pop()\n",
    "                operand1 = stack.pop()\n",
    "\n",
    "                if token == \"+\":\n",
    "                    result = operand1 + operand2\n",
    "                elif token == \"-\":\n",
    "                    result = operand1 - operand2\n",
    "                elif token == \"*\":\n",
    "                    result = operand1 * operand2\n",
    "                elif token == \"/\":\n",
    "                    result = int(operand1 / operand2)\n",
    "\n",
    "                stack.append(result)\n",
    "\n",
    "        return stack[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        # 如果是数字就入栈, 如果是运算符就取栈顶元素操作\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if token == \"+\":\n",
    "                    stack.append(int(a) + int(b))\n",
    "                if token == \"*\":\n",
    "                    stack.append(int(a) * int(b))\n",
    "                if token == \"-\":\n",
    "                    stack.append(int(b) - int(a))\n",
    "                if token == \"/\":\n",
    "                    stack.append(int(b) / int(a))\n",
    "            else:\n",
    "                stack.append(token)\n",
    "        return int(stack[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in \"+-*/\":\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                if token == '+':\n",
    "                    stack.append(num1 + num2)\n",
    "                elif token == '-':\n",
    "                    stack.append(num1 - num2)\n",
    "                elif token == '*':\n",
    "                    stack.append(num1 * num2)\n",
    "                else:\n",
    "                    if num1 * num2 >= 0:\n",
    "                        stack.append(floor(num1 / num2))\n",
    "                    else:\n",
    "                        stack.append(ceil(num1 / num2))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        numstack = []\n",
    "        for t in tokens:\n",
    "            if t.lstrip('-').isdigit():\n",
    "                numstack.append(int(t))\n",
    "                continue\n",
    "            if t == '+':\n",
    "                a = numstack.pop()\n",
    "                b = numstack.pop()\n",
    "                numstack.append(a+b)\n",
    "                continue\n",
    "            if t == '-':\n",
    "                a = numstack.pop()\n",
    "                b = numstack.pop()\n",
    "                numstack.append(b-a)\n",
    "                continue\n",
    "            if t == '*':\n",
    "                a = numstack.pop()\n",
    "                b = numstack.pop()\n",
    "                numstack.append(a*b)\n",
    "                continue\n",
    "            if t == '/':\n",
    "                a = numstack.pop()\n",
    "                b = numstack.pop()\n",
    "                if a * b < 0 and b % a != 0:\n",
    "                    numstack.append(b // a + 1)\n",
    "                else:\n",
    "                        numstack.append(b // a)\n",
    "        return numstack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for item in tokens:\n",
    "            if item not in {\"+\", \"-\", \"*\", \"/\"}:\n",
    "                stack.append(item)\n",
    "            else:\n",
    "                first, second = stack.pop(), stack.pop()\n",
    "                stack.append(\n",
    "                    int(eval(f\"{second}{item}{first}\"))\n",
    "                )\n",
    "        return int(stack[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            if not i in (\"+\", \"-\", \"*\", \"/\"):\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                c = int(eval(str(b) + i + str(a)))\n",
    "                stack.append(c)\n",
    "        return int(stack[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        res = []\n",
    "        for i in range(len(tokens)):\n",
    "            if tokens[i] == '+': res.append(res.pop() + res.pop())\n",
    "            elif tokens[i] == '-': res.append(-res.pop() + res.pop())\n",
    "            elif tokens[i] == '*': res.append(res.pop() * res.pop())\n",
    "            elif tokens[i] == '/': res.append(int(1/res.pop() * res.pop()))\n",
    "            else: res.append(int(tokens[i]))\n",
    "        return res.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y),}\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        mapping = {\"+\":lambda x,y:x+y,\n",
    "        \"-\":lambda x,y:x-y,\n",
    "        \"*\":lambda x,y:x*y,\n",
    "        \"/\":lambda x,y:int(x/y)}\n",
    "        for value in tokens:\n",
    "            if value not in mapping:\n",
    "                stack.append(int(value))\n",
    "            else:\n",
    "                num1 = stack.pop()\n",
    "                num2 = stack.pop()\n",
    "                stack.append(mapping[value](num2,num1))\n",
    "        return stack[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        def calculate(num1:int,num2:int,flag:str)->int:\n",
    "            if flag == \"+\":\n",
    "                return  num1+num2\n",
    "            elif  flag == '-':\n",
    "                return num1 - num2\n",
    "            elif  flag == '*':\n",
    "                return num1 *num2\n",
    "            elif flag == '/':\n",
    "                f =  -1 if num1 *num2 <0 else 1\n",
    "                return abs(num1)//abs(num2)*f\n",
    "\n",
    "        st = deque()\n",
    "        for token in tokens:\n",
    "            if  token  in ('+','-','*','/'):\n",
    "                num1 = int(st.pop())\n",
    "                num2 = int(st.pop())\n",
    "                t = calculate(num2,num1,token)\n",
    "                st.append(t)\n",
    "            else:\n",
    "                st.append(token)\n",
    "\n",
    "        return int(st.pop())\n",
    "        \n",
    "\n",
    "        \n",
    "   \n",
    " \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        # 是符号，就弹出临近的两个进行计算，是数字就压入栈\n",
    "        op = {\"+\":lambda x,y:x+y,\n",
    "            \"-\":lambda x,y:x-y,\n",
    "            \"*\":lambda x,y:x*y,\n",
    "            \"/\":lambda x,y:int(x/y)\n",
    "        }\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)\n",
    "            except ValueError:\n",
    "                num1 = stack.pop()\n",
    "                num2 = stack.pop()\n",
    "                num = op[token](num2,num1)\n",
    "            stack.append(num)#入栈\n",
    "        return stack[0]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack=[]\n",
    "        fuhao='+-*/'\n",
    "        for i in tokens:\n",
    "            if i not in fuhao:stack.append(int(i))\n",
    "            else:\n",
    "                if i=='+':\n",
    "                    a=stack.pop()\n",
    "                    b=stack.pop()\n",
    "                    stack.append(b+a)\n",
    "                if i=='-':\n",
    "                    a=stack.pop()\n",
    "                    b=stack.pop()\n",
    "                    stack.append(b-a)\n",
    "                if i=='*':\n",
    "                    a=stack.pop()\n",
    "                    b=stack.pop()\n",
    "                    stack.append(b*a)\n",
    "                if i=='/':\n",
    "                    a=stack.pop()\n",
    "                    b=stack.pop()\n",
    "                    kk=b//a\n",
    "                    if b%a!=0 and kk<0:kk+=1\n",
    "                    stack.append(kk)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        stack = []\n",
    "        calc = {'+': lambda x, y: x + y,\n",
    "                '-': lambda x, y: x - y,\n",
    "                '*': lambda x, y: x * y,\n",
    "                '/': lambda x, y: int(x / y), }\n",
    "        for i in tokens:\n",
    "            if i in calc:\n",
    "                num2, num1 = stack.pop(), stack.pop()\n",
    "                stack.append(calc[i](num1, num2))\n",
    "            else:\n",
    "                stack.append(int(i))\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from operator import add, sub, mul\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        op_to_binary_fn = {\n",
    "            \"+\": add,\n",
    "            \"-\": sub,\n",
    "            \"*\": mul,\n",
    "            \"/\": lambda x, y: int(x / y)  # 由于只需要整数部分，特别处理除法\n",
    "        }\n",
    "\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)  # 尝试将标记转换为整数\n",
    "            except ValueError:  # 如果转换失败，说明是运算符\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                num = op_to_binary_fn[token](num1, num2)  # 应用运算符进行计算\n",
    "            finally:\n",
    "                stack.append(num)  # 将结果压回栈中\n",
    "\n",
    "        return stack[0]  # 最终的计算结果在栈顶\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token in (['+', '-', '*', '/']):\n",
    "                num1 = stack.pop()\n",
    "                num2 = stack.pop()\n",
    "                if token == '+':\n",
    "                    stack.append(num1 + num2)\n",
    "                elif token == '-':\n",
    "                    stack.append(-num1 + num2)\n",
    "                elif token == '*':\n",
    "                    stack.append(num1 * num2)\n",
    "                else:\n",
    "                    stack.append(int(num2 / num1))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        s = []\n",
    "        operator = set([\"+\", \"-\", \"*\", \"/\"])\n",
    "        for token in tokens:\n",
    "            if token not in operator:\n",
    "                s.append(token)\n",
    "            else:\n",
    "                r = int(s.pop())\n",
    "                l = int(s.pop())\n",
    "                if token == \"+\":\n",
    "                    s.append(str(l+r))\n",
    "                elif token == \"-\":\n",
    "                    s.append(str(l-r))\n",
    "                elif token == \"*\":\n",
    "                    s.append(str(l*r))\n",
    "                elif token == \"/\":\n",
    "                    s.append(str(int(l/r)))\n",
    "        return int(s.pop())\n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        opDict = {\"+\": lambda x,y: x + y, \"-\": lambda x,y: x - y, \"*\": lambda x,y: x * y, \"/\": lambda x,y: int(x / y)}\n",
    "        numStack = []\n",
    "        for token in tokens:\n",
    "            if token in opDict:\n",
    "                right = numStack.pop()\n",
    "                left = numStack.pop()\n",
    "                numStack.append(opDict[token](left, right))            \n",
    "            else:\n",
    "                numStack.append(int(token))\n",
    "        return numStack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "\n",
    "        def cal(c1, c2, op):\n",
    "            v1, v2 = int(c1), int(c2)\n",
    "            if op == '+':\n",
    "                return v1 + v2\n",
    "            elif op == '-':\n",
    "                return v1 - v2\n",
    "            elif op == '*':\n",
    "                return v1 * v2\n",
    "            elif op == '/':\n",
    "                return int(v1 / v2)\n",
    "\n",
    "        for c in tokens:\n",
    "            if c not in \"+-*/\":\n",
    "                stack.append(int(c))\n",
    "            else:\n",
    "                v2 = stack.pop()\n",
    "                v1 = stack.pop()\n",
    "                stack.append(cal(v1, v2, c))\n",
    "\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        state = []\n",
    "        for i in range(0,len(tokens)):\n",
    "            if tokens[i] not in ['+','-','*','/']:\n",
    "                state.append(int(tokens[i]))\n",
    "            else:\n",
    "                if tokens[i] == '+':\n",
    "                    value = state[-2] + state[-1]\n",
    "                elif tokens[i] == '-':\n",
    "                    value = state[-2] - state[-1]\n",
    "                elif tokens[i] == '*':\n",
    "                    value = state[-2] * state[-1]\n",
    "                else:\n",
    "                    if state[-2] * state[-1] >= 0:\n",
    "                        value = abs(state[-2]) // abs(state[-1])\n",
    "                    else:\n",
    "                        value = - (abs(state[-2]) // abs(state[-1]))\n",
    "                \n",
    "                del state[-1]\n",
    "                del state[-1]\n",
    "                state.append(value)\n",
    "            #print(state)\n",
    "\n",
    "        return state[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        op_to_binary_fn = {\n",
    "            \"+\": add,\n",
    "            \"-\": sub,\n",
    "            \"*\": mul,\n",
    "            \"/\": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致\n",
    "        }\n",
    "\n",
    "        n = len(tokens)\n",
    "        stack = [0] * ((n + 1) // 2)\n",
    "        index = -1\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                num = int(token)\n",
    "                index += 1\n",
    "                stack[index] = num\n",
    "            except ValueError:\n",
    "                index -= 1\n",
    "                stack[index] = op_to_binary_fn[token](stack[index], stack[index + 1])\n",
    "            \n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in tokens:\n",
    "            \n",
    "            if i in ['+','-','*','/']:\n",
    "                a = stack.pop()\n",
    "                b = stack.pop()\n",
    "                if i ==\"+\":\n",
    "                    stack.append(int(a) + int(b))\n",
    "                if i =='*':\n",
    "                    stack.append(int(b) * int(a))\n",
    "                if i =='-':\n",
    "                    stack.append(int(b) - int(a))\n",
    "                if i =='/':\n",
    "                    stack.append(int(b) / int(a))\n",
    "\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return int(stack[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        # print('-11'.isdigit())\n",
    "        for item in tokens:\n",
    "            if len(item) > 1 or item.isdigit():\n",
    "                stack.append(int(item))\n",
    "            else:\n",
    "                # print(item, stack)\n",
    "                num1 = stack[-1]\n",
    "                stack.pop()\n",
    "                num2 = stack[-1]\n",
    "                stack.pop()\n",
    "                res = 0\n",
    "                if item == '+':\n",
    "                    res = num1 + num2\n",
    "                elif item == '-':\n",
    "                    res = num2 - num1\n",
    "                elif item == '*':\n",
    "                    res = num1 * num2\n",
    "                elif item == '/':\n",
    "                    res = abs(num2) // abs(num1)\n",
    "                    if (num2 < 0 and num1 > 0) or (num2 > 0 and num1 < 0):\n",
    "                        res = - res\n",
    "                stack.append(res)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "OP_FUNC = {\n",
    "    '+': lambda a, b: a + b,\n",
    "    '-': lambda a, b: a - b,\n",
    "    '*': lambda a, b: a * b,\n",
    "    '/': lambda a, b: int(a / b),\n",
    "}\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        nums = []\n",
    "        for c in tokens:\n",
    "            try:\n",
    "                nums.append(int(c))\n",
    "            except ValueError:\n",
    "                func = OP_FUNC[c]\n",
    "                right = nums.pop()\n",
    "                left = nums.pop()\n",
    "                nums.append(func(left, right))\n",
    "        return nums.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        symbol = ['+', '-', '*', '/']\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            if i not in symbol:\n",
    "                stack.append(i)\n",
    "            elif i == '+':\n",
    "                a = int(stack.pop())\n",
    "                b = int(stack.pop())\n",
    "                stack.append(b+a)\n",
    "            elif i == '-':\n",
    "                a = int(stack.pop())\n",
    "                b = int(stack.pop())\n",
    "                stack.append(b-a)\n",
    "            elif i == '*':\n",
    "                a = int(stack.pop())\n",
    "                b = int(stack.pop())\n",
    "                stack.append(b * a)\n",
    "            elif i == '/':\n",
    "                a = int(stack.pop())\n",
    "                b = int(stack.pop())\n",
    "                # stack.append(b // a) 不能用// 因为//是向下取整，如果是负数需要向上取整\n",
    "                stack.append(int(b / a))\n",
    "        return int(stack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    op_map = {'+':add,'-':sub,'*':mul,'/':lambda x,y:int(x/y)}\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token not in ['+','-','*','/']:\n",
    "                stack.append(int(token))\n",
    "            else:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append(self.op_map[token](num1,num2))\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        num = []\n",
    "        for c in tokens:\n",
    "            # print('c--',c,c.isdigit())\n",
    "            if c.isdigit() or len(c) > 1:\n",
    "                num.append(int(c))\n",
    "            elif c == '+' or c == '-' or c == '*' or c == '/':\n",
    "                num2 = num.pop()\n",
    "                num1 = num.pop()\n",
    "                if c == '+':\n",
    "                    res = num1 + num2\n",
    "                elif c == '-':\n",
    "                    res = num1 - num2\n",
    "                elif c == '*':\n",
    "                    res = num1 * num2\n",
    "                elif c == '/':\n",
    "                    res = int(num1 / num2)\n",
    "                num.append(res)\n",
    "        return int(num[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack=[]\n",
    "        a=['+','-','*','/']\n",
    "        for x in tokens:\n",
    "            if x not in a:\n",
    "                stack.append(int(x))\n",
    "            elif x==a[0]:\n",
    "                stack.append(stack[-1]+stack[-2])\n",
    "                stack.pop(-2)\n",
    "                stack.pop(-2)\n",
    "            elif x==a[1]:\n",
    "                stack.append(stack[-2]-stack[-1])\n",
    "                stack.pop(-2)\n",
    "                stack.pop(-2)\n",
    "            elif x==a[2]:\n",
    "                stack.append(stack[-1]*stack[-2])\n",
    "                stack.pop(-2)\n",
    "                stack.pop(-2)\n",
    "            else:\n",
    "                stack.append(int(stack[-2]/stack[-1]))\n",
    "                stack.pop(-2)\n",
    "                stack.pop(-2)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        que=collections.deque()\n",
    "        signs=['+','-','*','/']\n",
    "        for token in tokens:\n",
    "            # if token=='+' or token=='-' or token=='*' or token=='/':\n",
    "            if token not in signs:\n",
    "                que.append(int(token))\n",
    "            else:\n",
    "                l1=que.pop()\n",
    "                l2=que.pop()\n",
    "                if token=='+':\n",
    "                    que.append(l1+l2)\n",
    "                elif token=='*':\n",
    "                    que.append(l1*l2)\n",
    "                elif token=='-':\n",
    "                    que.append(l2-l1)\n",
    "                elif token=='/':\n",
    "                    que.append(int(l2/l1))\n",
    "\n",
    "\n",
    "        return que[0]\n",
    "        # stack=[]\n",
    "        # calc={'+':lambda x,y:x+y,\n",
    "        #       '-':lambda x,y:x-y,\n",
    "        #       '*':lambda x,y:x*y,\n",
    "        #       '/':lambda x,y:int(x/y)}\n",
    "        # for i in tokens:\n",
    "        #     if i in calc:\n",
    "        #         num2,num1=stack.pop(),stack.pop()\n",
    "        #         stack.append(calc[i](num1,num2))\n",
    "        #     else:\n",
    "        #         stack.append(int(i))\n",
    "        # return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            if i not in '/*-+':\n",
    "                stack.append(int(i))\n",
    "            else:\n",
    "                b = stack.pop()\n",
    "                a = stack.pop()\n",
    "            if i == '+':\n",
    "                res = a + b\n",
    "                stack.append(int(res))\n",
    "            if i == '-':\n",
    "                res = a - b\n",
    "                stack.append(int(res))\n",
    "            if i == '*':\n",
    "                res = a * b\n",
    "                stack.append(int(res))\n",
    "            if i == '/':\n",
    "                res = a / b\n",
    "                stack.append(int(res))\n",
    "        return stack[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
